import java.awt.print.Printable;


import com.mj.printer.BinaryTrees;
import com.sun.org.apache.xalan.internal.xsltc.compiler.sym;

import BinaryTrees.AVLTree;
import BinaryTrees.BinaryTree;
import LeetCode.ListNode;
import LinkedListAndArray.ArrayList;
import LinkedListAndArray.Asserts;
import LinkedListAndArray.CircleLinkedList;
import LinkedListAndArray.LinkedList;
import LinkedListAndArray.List;
import LinkedListAndArray.SingleCircleLinkedList;
import LinkedListAndArray.SingleLinkedList;
import LinkedListAndArray.SingleLinkedList_VirtualHead;
import StackAndQueue.CircleDeque;
import StackAndQueue.CircleQueue;
import StackAndQueue.Deque;
import StackAndQueue.Queue;
import StackAndQueue.Stack;
import 二叉树.BinarySearchTree;
import 二叉树.BinarySearchTree.Visitor;
import 二叉树.BinaryTreeInterface;
//import 二叉搜索树.bin

@SuppressWarnings("unused")
public class main {

	public static void main(String[] args) {

//		testArrayList();
//		
//		testSingleLinkedList();
//		
//		reversalList();
//		
//		testLinkedList();
//		
//		testSingleCircleLinkedList();
//
//		testCircleLinkedList();

//		testJosephus();

//		testStack();

//		testQueue();

//		testDeque();

//		testCircleQueue();

//		testCircleDeque();	
		
//		testBinaryTreePrint();
		
		testAVLTree();
	}
	
	static void testAVLTree() {
		Integer data[] = new Integer[] {
				67, 52, 92, 96, 53, 95, 13, 63, 34, 82, 76, 54, 9, 68, 39
		};
		
		AVLTree<Integer> avl = new AVLTree<>();
		for (int i = 0; i < data.length; i++) {
			avl.add(data[i]);
			System.out.println("【" + data[i] + "】");
			BinaryTrees.println(avl);
			System.out.println("---------------------------------------");
		}
		
		System.out.println("============开始删除============");
		
		for (int i = 0; i < data.length; i++) {
			avl.remove(data[i]);
			System.out.println("【" + data[i] + "】");
			BinaryTrees.println(avl);
			System.out.println("---------------------------------------");
		}
		
		
//		BinaryTrees.println(avl);
	}
	
	static void testBinaryTreePrint() {
		Integer data[] = new Integer[] {
				7, 4, 9, 2, 1
		};
		
		BinarySearchTree<Integer> bstBinarySearchTree = new BinarySearchTree<Integer>();
			
		for (int i = 0; i < data.length; i++) {
			bstBinarySearchTree.add(data[i]);
		}
		BinaryTrees.println(bstBinarySearchTree);
		
		System.out.println(bstBinarySearchTree.toString());

		
		bstBinarySearchTree.preorder(new Visitor<Integer>() {
			@Override
			public boolean visitor(Integer element) {
				System.out.print(element + " ");
				return element == 2 ? true : false;
			}
		});
		System.out.println();
		
		bstBinarySearchTree.inorder(new Visitor<Integer>() {
			@Override
			public boolean visitor(Integer element) {
				System.out.print(element + " ");
				return element == 4 ? true : false;
			}
		});
		System.out.println();
		
		bstBinarySearchTree.postorder(new Visitor<Integer>() {
			@Override
			public boolean visitor(Integer element) {
				System.out.print(element + " ");
				return element == 4 ? true : false;
			}
		});
		System.out.println();
		
		bstBinarySearchTree.levelOrder(new Visitor<Integer>() {
			@Override
			public boolean visitor(Integer element) {
				System.out.print(element + " ");
				return element == 9 ? true : false;
			}
		});
		System.out.println();
		
		System.out.println("..........");
		
		System.out.println(bstBinarySearchTree.height());
		
		System.out.println("..........");
		
	
	}

	/**
	 * 测试方法(适用于链表&数组)
	 */
	static void testList(List<Integer> list) {
		list.add(11);
		list.add(22);
		list.add(33);
		list.add(44);

		list.add(0, 55); // [55, 11, 22, 33, 44]
		list.add(2, 66); // [55, 11, 66, 22, 33, 44]
		list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]

		list.remove(0); // [11, 66, 22, 33, 44, 77]
		list.remove(2); // [11, 66, 33, 44, 77]
		list.remove(list.size() - 1); // [11, 66, 33, 44]

		Asserts.test(list.indexOf(44) == 3);
		Asserts.test(list.indexOf(22) == List.ELEMENT_NOT_FOUND);
		Asserts.test(list.contains(33));
		Asserts.test(list.get(0) == 11);
		Asserts.test(list.get(1) == 66);
		Asserts.test(list.get(list.size() - 1) == 44);

		System.out.println(list);
	}

	// 测试循环双端队列
	static void testCircleDeque() {
		CircleDeque<Object> queue = new CircleDeque<>();
		System.out.println("isEmpty:" + queue.isEmpty());
		for (int i = 0; i < 15; i++) {
			queue.enQueueRear(i + 1);
		}
		System.out.println("front:" + queue.front());
		System.out.println("size:" + queue.size());

		System.out.println("deQueueFront:" + queue.deQueueFront());

		System.out.println("size:" + queue.size());
		System.out.println("front:" + queue.front());

		int length = queue.size() - 1;
		for (int i = 0; i < length; i++) {
			System.out.println("deQueueRear:" + queue.deQueueRear());
		}

		System.out.println("front:" + queue.front());
		System.out.println("rear:" + queue.rear());
		System.out.println("size:" + queue.size());
		queue.clear();
		System.out.println("isEmpty:" + queue.isEmpty());
	}

	// 测试循环队列
	static void testCircleQueue() {
		CircleQueue<Object> queue = new CircleQueue<>();
		System.out.println("isEmpty:" + queue.isEmpty());
		for (int i = 0; i < 15; i++) {
			queue.enQueue(i + 1);
		}
		System.out.println("top:" + queue.front());
		System.out.println("isEmpty:" + queue.isEmpty());
		System.out.println("size:" + queue.size());

//		System.out.println("pop:" + queue.deQueue());

		System.out.println("size:" + queue.size());
		System.out.println("top:" + queue.front());
		int length = (queue.size() >> 1) + 2;
		for (int i = 0; i < length; i++) {
			System.out.println("pop:" + queue.deQueue());
		}

		for (int i = 0; i < 3; i++) {
			queue.enQueue(10 + 1);
		}

		System.out.println("top:" + queue.front());
		System.out.println("size:" + queue.size());
		queue.clear();
		System.out.println("isEmpty:" + queue.isEmpty());
	}

	// 测试双端队列
	static void testDeque() {
		Deque<Object> queue = new Deque<>();
		System.out.println("isEmpty:" + queue.isEmpty());
		for (int i = 0; i < 10; i++) {
			queue.enQueueRear(i + 1);
		}
		System.out.println("front:" + queue.front());
		System.out.println("isEmpty:" + queue.isEmpty());
		System.out.println("size:" + queue.size());

		System.out.println("deQueueFront:" + queue.deQueueFront());

		System.out.println("size:" + queue.size());
		System.out.println("front:" + queue.front());
		int length = queue.size() - 1;
		for (int i = 0; i < length; i++) {
			System.out.println("deQueueRear:" + queue.deQueueRear());
		}

		System.out.println("front:" + queue.front());
		System.out.println("rear:" + queue.rear());
		System.out.println("size:" + queue.size());
		queue.clear();
		System.out.println("isEmpty:" + queue.isEmpty());
	}

	// 测试队列
	static void testQueue() {
		Queue<Object> queue = new Queue<>();
		System.out.println("isEmpty:" + queue.isEmpty());
		for (int i = 0; i < 10; i++) {
			queue.enQueue(i + 1);
		}
		System.out.println("top:" + queue.front());
		System.out.println("isEmpty:" + queue.isEmpty());
		System.out.println("size:" + queue.size());

		System.out.println("pop:" + queue.deQueue());

		System.out.println("size:" + queue.size());
		System.out.println("top:" + queue.front());
		int length = queue.size() - 1;
		for (int i = 0; i < length; i++) {
			System.out.println("pop:" + queue.deQueue());
		}
		System.out.println("top:" + queue.front());
		System.out.println("size:" + queue.size());
		queue.clear();
		System.out.println("isEmpty:" + queue.isEmpty());
	}

	// 测试栈
	static void testStack() {
		Stack<Object> stack = new Stack<>();
		System.out.println("isEmpty:" + stack.isEmpty());
		for (int i = 0; i < 10; i++) {
			stack.push(i + 1);
		}
		System.out.println("top:" + stack.top());
		System.out.println("isEmpty:" + stack.isEmpty());
		System.out.println("size:" + stack.size());

		System.out.println("pop:" + stack.pop());

		System.out.println("size:" + stack.size());
		System.out.println("top:" + stack.top());
		int length = stack.size() - 1;
		for (int i = 0; i < length; i++) {
			System.out.println("pop:" + stack.pop());
		}
		System.out.println("top:" + stack.top());
		System.out.println("size:" + stack.size());
		stack.clear();
		System.out.println("isEmpty:" + stack.isEmpty());
	}

	// 测试约瑟夫问题答案
	private static void testJosephus() {
		CircleLinkedList<Integer> list = new CircleLinkedList<>();
		for (int i = 1; i <= 8; i++) {
			list.add(i);
		}

		// 指向头结点（指向1）
		list.reset();

		while (!list.isEmpty()) {
			list.next();
			list.next();
			System.out.println(list.remove());
		}
	}

	// 测试双向循环链表.
	public static void testCircleLinkedList() {
		CircleLinkedList<Integer> list = new CircleLinkedList<>();
		testList(list);
	}

	// 测试单向循环链表.
	public static void testSingleCircleLinkedList() {
		SingleCircleLinkedList<Integer> list = new SingleCircleLinkedList<>();
		testList(list);
	}

	/*
	 * 测试链表(双向链表)
	 */
	static private void testLinkedList() {
		LinkedList<Integer> linkedList = new LinkedList<>();
		testList(linkedList);
	}

	// 反转链表
	@SuppressWarnings("unused")
	static private void reversalList() {
		SingleLinkedList<Integer> linkedList = new SingleLinkedList<>();
		testList(linkedList);
	}

	static private void testSingleLinkedList() {
		SingleLinkedList_VirtualHead<Integer> linkedList = new SingleLinkedList_VirtualHead<>();
		testList(linkedList);
	}

	@SuppressWarnings("unused")
	static private void testArrayList() {
		ArrayList<Integer> list1ArrayList = new ArrayList<>();
		testList(list1ArrayList);

		ArrayList<Object> list = new ArrayList<>();

		System.out.println(list.isEmpty() ? "空数组" : "非空数组");

		for (int i = 0; i < 17; i++) {
			list.add(i);
		}

		System.out.println("数组长度:" + list.length() + ", 数组元素个数:" + list.size());

		System.out.println(list.isEmpty() ? "空数组" : "非空数组");

		System.out.println(list.toString());
		list.remove(2);
		System.out.println(list.toString());
		list.remove(5);
		System.out.println(list.toString());
		list.remove(7);
		System.out.println("" + list.size());

//        for (int i = 0; i < 10; i++) {
//            list.remove(0);
//        }
//        Log.d("ArrayList", "数组长度:" + list.length() + ", 数组元素个数:" + list.size());
//
//        list.add(2, "qq");
//        list.add(list.size(), "cc");
//        Log.d("ArrayList",list.toString());
//
//        list.remove(0);
//        Log.d("ArrayList",list.toString());
//
		list.clear();
		System.out.println("数组长度:" + list.length() + ", 数组元素个数:" + list.size());
		Asserts.test(10 == list.length());
	}
}
